package linkList

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func sortList1(head *ListNode) *ListNode {
	if head == nil {
		return head
	}

	length := 0
	for node := head; node != nil; node = node.Next {
		length++
	}

	dummyHead := &ListNode{Next: head}
	for subLength := 1; subLength < length; subLength <<= 1 {
		// 这里必须是dummyHead.Next，因为在第一次将两份链表merge的时，如果第二份的第一个值比第一份的第一个值要小，则dummyNode的next指针
		// 是会指向第二份链表的第一个节点的，也就不是head了(head是第一份的第一个节点)
		prev, cur := dummyHead, dummyHead.Next
		for cur != nil {
			head1 := cur
			for i := 1; i < subLength && cur.Next != nil; i++ {
				cur = cur.Next
			}

			head2 := cur.Next
			cur.Next = nil
			cur = head2
			for i := 1; i < subLength && cur != nil && cur.Next != nil; i++ {
				cur = cur.Next
			}

			var next *ListNode
			if cur != nil {
				next = cur.Next
				cur.Next = nil
			}

			prev.Next = merge(head1, head2)

			for prev.Next != nil {
				prev = prev.Next
			}
			cur = next
		}
	}
	return dummyHead.Next
}

// 通过cur指针，每一轮将链表分成每份一个节点/两个节点.....N个节点
// 第一次每份一个节点,将两个节点合并起来,然后第二次节点两份,将这两份已排好序的节点合并起来....
func sortList(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}
	// 计算链表总节点个数
	length := 0
	for cur := head; cur != nil; cur = cur.Next {
		length++
	}

	dummyNode := &ListNode{Next: head}
	// subLength是每一轮将节点均分时每一份节点的个数
	for subLength := 1; subLength < length; subLength <<= 1 {
		pre, cur := dummyNode, head
		for cur != nil {
			// 截取第一份，head1作为合并两份链表时，第一份链表的头节点
			head1 := cur
			// 这里之所以用cur.Next != nil 是因为 如果用cur != nil，则可能第一份分完后cur指向了nil节点，没有第二份了
			for i := 1; i < subLength && cur.Next != nil; i++ {
				cur = cur.Next
			}

			// 截取第二份
			head2 := cur.Next
			// 截断第一份
			cur.Next = nil
			cur = head2
			// 这里使用cur.Next != nil 是为了 cur不为nil，从而使得 next = cur.Next不会报错
			for i := 1; i < subLength && cur != nil && cur.Next != nil; i++ {
				cur = cur.Next
			}

			// 截断第二份
			var next *ListNode
			if cur != nil {
				next = cur.Next
				cur.Next = nil
			}

			// 合并两份节点
			pre.Next = merge(head1, head2)
			for pre.Next != nil {
				pre = pre.Next
			}

			cur = next
		}
	}
	return dummyNode.Next
}

// 合并两个已经有序的链表，使合并后的链表也有序
func merge(head1, head2 *ListNode) *ListNode {
	dummyNode := &ListNode{}
	cur, p1, p2 := dummyNode, head1, head2
	for p1 != nil && p2 != nil {
		if p1.Val <= p2.Val {
			cur.Next = p1
			p1 = p1.Next
		} else {
			cur.Next = p2
			p2 = p2.Next
		}
		cur = cur.Next
	}

	if p1 != nil {
		cur.Next = p1
	}
	if p2 != nil {
		cur.Next = p2
	}
	return dummyNode.Next
}
